{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python机器学习（第15期）第6课书面作业\n",
    "学号：113727\n",
    "\n",
    "**书面作业**  \n",
    "1 自行寻找数据集，用python编程实现以下算法中至少一种半监督学习算法  \n",
    "1）self-training  \n",
    "2）约束k-means  \n",
    "3）约束种子k-means  \n",
    "抓图实验过程，并算出准确率指标。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 self-training算法\n",
    "### 1.1 数据集选择\n",
    "选取经典乳腺癌数据集。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>mean radius</th>\n",
       "      <th>mean texture</th>\n",
       "      <th>mean perimeter</th>\n",
       "      <th>mean area</th>\n",
       "      <th>mean smoothness</th>\n",
       "      <th>mean compactness</th>\n",
       "      <th>mean concavity</th>\n",
       "      <th>mean concave points</th>\n",
       "      <th>mean symmetry</th>\n",
       "      <th>mean fractal dimension</th>\n",
       "      <th>...</th>\n",
       "      <th>worst texture</th>\n",
       "      <th>worst perimeter</th>\n",
       "      <th>worst area</th>\n",
       "      <th>worst smoothness</th>\n",
       "      <th>worst compactness</th>\n",
       "      <th>worst concavity</th>\n",
       "      <th>worst concave points</th>\n",
       "      <th>worst symmetry</th>\n",
       "      <th>worst fractal dimension</th>\n",
       "      <th>target</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>17.99</td>\n",
       "      <td>10.38</td>\n",
       "      <td>122.80</td>\n",
       "      <td>1001.0</td>\n",
       "      <td>0.11840</td>\n",
       "      <td>0.27760</td>\n",
       "      <td>0.30010</td>\n",
       "      <td>0.14710</td>\n",
       "      <td>0.2419</td>\n",
       "      <td>0.07871</td>\n",
       "      <td>...</td>\n",
       "      <td>17.33</td>\n",
       "      <td>184.60</td>\n",
       "      <td>2019.0</td>\n",
       "      <td>0.16220</td>\n",
       "      <td>0.66560</td>\n",
       "      <td>0.7119</td>\n",
       "      <td>0.2654</td>\n",
       "      <td>0.4601</td>\n",
       "      <td>0.11890</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>20.57</td>\n",
       "      <td>17.77</td>\n",
       "      <td>132.90</td>\n",
       "      <td>1326.0</td>\n",
       "      <td>0.08474</td>\n",
       "      <td>0.07864</td>\n",
       "      <td>0.08690</td>\n",
       "      <td>0.07017</td>\n",
       "      <td>0.1812</td>\n",
       "      <td>0.05667</td>\n",
       "      <td>...</td>\n",
       "      <td>23.41</td>\n",
       "      <td>158.80</td>\n",
       "      <td>1956.0</td>\n",
       "      <td>0.12380</td>\n",
       "      <td>0.18660</td>\n",
       "      <td>0.2416</td>\n",
       "      <td>0.1860</td>\n",
       "      <td>0.2750</td>\n",
       "      <td>0.08902</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>19.69</td>\n",
       "      <td>21.25</td>\n",
       "      <td>130.00</td>\n",
       "      <td>1203.0</td>\n",
       "      <td>0.10960</td>\n",
       "      <td>0.15990</td>\n",
       "      <td>0.19740</td>\n",
       "      <td>0.12790</td>\n",
       "      <td>0.2069</td>\n",
       "      <td>0.05999</td>\n",
       "      <td>...</td>\n",
       "      <td>25.53</td>\n",
       "      <td>152.50</td>\n",
       "      <td>1709.0</td>\n",
       "      <td>0.14440</td>\n",
       "      <td>0.42450</td>\n",
       "      <td>0.4504</td>\n",
       "      <td>0.2430</td>\n",
       "      <td>0.3613</td>\n",
       "      <td>0.08758</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>11.42</td>\n",
       "      <td>20.38</td>\n",
       "      <td>77.58</td>\n",
       "      <td>386.1</td>\n",
       "      <td>0.14250</td>\n",
       "      <td>0.28390</td>\n",
       "      <td>0.24140</td>\n",
       "      <td>0.10520</td>\n",
       "      <td>0.2597</td>\n",
       "      <td>0.09744</td>\n",
       "      <td>...</td>\n",
       "      <td>26.50</td>\n",
       "      <td>98.87</td>\n",
       "      <td>567.7</td>\n",
       "      <td>0.20980</td>\n",
       "      <td>0.86630</td>\n",
       "      <td>0.6869</td>\n",
       "      <td>0.2575</td>\n",
       "      <td>0.6638</td>\n",
       "      <td>0.17300</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>20.29</td>\n",
       "      <td>14.34</td>\n",
       "      <td>135.10</td>\n",
       "      <td>1297.0</td>\n",
       "      <td>0.10030</td>\n",
       "      <td>0.13280</td>\n",
       "      <td>0.19800</td>\n",
       "      <td>0.10430</td>\n",
       "      <td>0.1809</td>\n",
       "      <td>0.05883</td>\n",
       "      <td>...</td>\n",
       "      <td>16.67</td>\n",
       "      <td>152.20</td>\n",
       "      <td>1575.0</td>\n",
       "      <td>0.13740</td>\n",
       "      <td>0.20500</td>\n",
       "      <td>0.4000</td>\n",
       "      <td>0.1625</td>\n",
       "      <td>0.2364</td>\n",
       "      <td>0.07678</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>564</th>\n",
       "      <td>21.56</td>\n",
       "      <td>22.39</td>\n",
       "      <td>142.00</td>\n",
       "      <td>1479.0</td>\n",
       "      <td>0.11100</td>\n",
       "      <td>0.11590</td>\n",
       "      <td>0.24390</td>\n",
       "      <td>0.13890</td>\n",
       "      <td>0.1726</td>\n",
       "      <td>0.05623</td>\n",
       "      <td>...</td>\n",
       "      <td>26.40</td>\n",
       "      <td>166.10</td>\n",
       "      <td>2027.0</td>\n",
       "      <td>0.14100</td>\n",
       "      <td>0.21130</td>\n",
       "      <td>0.4107</td>\n",
       "      <td>0.2216</td>\n",
       "      <td>0.2060</td>\n",
       "      <td>0.07115</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>565</th>\n",
       "      <td>20.13</td>\n",
       "      <td>28.25</td>\n",
       "      <td>131.20</td>\n",
       "      <td>1261.0</td>\n",
       "      <td>0.09780</td>\n",
       "      <td>0.10340</td>\n",
       "      <td>0.14400</td>\n",
       "      <td>0.09791</td>\n",
       "      <td>0.1752</td>\n",
       "      <td>0.05533</td>\n",
       "      <td>...</td>\n",
       "      <td>38.25</td>\n",
       "      <td>155.00</td>\n",
       "      <td>1731.0</td>\n",
       "      <td>0.11660</td>\n",
       "      <td>0.19220</td>\n",
       "      <td>0.3215</td>\n",
       "      <td>0.1628</td>\n",
       "      <td>0.2572</td>\n",
       "      <td>0.06637</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>566</th>\n",
       "      <td>16.60</td>\n",
       "      <td>28.08</td>\n",
       "      <td>108.30</td>\n",
       "      <td>858.1</td>\n",
       "      <td>0.08455</td>\n",
       "      <td>0.10230</td>\n",
       "      <td>0.09251</td>\n",
       "      <td>0.05302</td>\n",
       "      <td>0.1590</td>\n",
       "      <td>0.05648</td>\n",
       "      <td>...</td>\n",
       "      <td>34.12</td>\n",
       "      <td>126.70</td>\n",
       "      <td>1124.0</td>\n",
       "      <td>0.11390</td>\n",
       "      <td>0.30940</td>\n",
       "      <td>0.3403</td>\n",
       "      <td>0.1418</td>\n",
       "      <td>0.2218</td>\n",
       "      <td>0.07820</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>567</th>\n",
       "      <td>20.60</td>\n",
       "      <td>29.33</td>\n",
       "      <td>140.10</td>\n",
       "      <td>1265.0</td>\n",
       "      <td>0.11780</td>\n",
       "      <td>0.27700</td>\n",
       "      <td>0.35140</td>\n",
       "      <td>0.15200</td>\n",
       "      <td>0.2397</td>\n",
       "      <td>0.07016</td>\n",
       "      <td>...</td>\n",
       "      <td>39.42</td>\n",
       "      <td>184.60</td>\n",
       "      <td>1821.0</td>\n",
       "      <td>0.16500</td>\n",
       "      <td>0.86810</td>\n",
       "      <td>0.9387</td>\n",
       "      <td>0.2650</td>\n",
       "      <td>0.4087</td>\n",
       "      <td>0.12400</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>568</th>\n",
       "      <td>7.76</td>\n",
       "      <td>24.54</td>\n",
       "      <td>47.92</td>\n",
       "      <td>181.0</td>\n",
       "      <td>0.05263</td>\n",
       "      <td>0.04362</td>\n",
       "      <td>0.00000</td>\n",
       "      <td>0.00000</td>\n",
       "      <td>0.1587</td>\n",
       "      <td>0.05884</td>\n",
       "      <td>...</td>\n",
       "      <td>30.37</td>\n",
       "      <td>59.16</td>\n",
       "      <td>268.6</td>\n",
       "      <td>0.08996</td>\n",
       "      <td>0.06444</td>\n",
       "      <td>0.0000</td>\n",
       "      <td>0.0000</td>\n",
       "      <td>0.2871</td>\n",
       "      <td>0.07039</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>569 rows × 31 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     mean radius  mean texture  mean perimeter  mean area  mean smoothness  \\\n",
       "0          17.99         10.38          122.80     1001.0          0.11840   \n",
       "1          20.57         17.77          132.90     1326.0          0.08474   \n",
       "2          19.69         21.25          130.00     1203.0          0.10960   \n",
       "3          11.42         20.38           77.58      386.1          0.14250   \n",
       "4          20.29         14.34          135.10     1297.0          0.10030   \n",
       "..           ...           ...             ...        ...              ...   \n",
       "564        21.56         22.39          142.00     1479.0          0.11100   \n",
       "565        20.13         28.25          131.20     1261.0          0.09780   \n",
       "566        16.60         28.08          108.30      858.1          0.08455   \n",
       "567        20.60         29.33          140.10     1265.0          0.11780   \n",
       "568         7.76         24.54           47.92      181.0          0.05263   \n",
       "\n",
       "     mean compactness  mean concavity  mean concave points  mean symmetry  \\\n",
       "0             0.27760         0.30010              0.14710         0.2419   \n",
       "1             0.07864         0.08690              0.07017         0.1812   \n",
       "2             0.15990         0.19740              0.12790         0.2069   \n",
       "3             0.28390         0.24140              0.10520         0.2597   \n",
       "4             0.13280         0.19800              0.10430         0.1809   \n",
       "..                ...             ...                  ...            ...   \n",
       "564           0.11590         0.24390              0.13890         0.1726   \n",
       "565           0.10340         0.14400              0.09791         0.1752   \n",
       "566           0.10230         0.09251              0.05302         0.1590   \n",
       "567           0.27700         0.35140              0.15200         0.2397   \n",
       "568           0.04362         0.00000              0.00000         0.1587   \n",
       "\n",
       "     mean fractal dimension  ...  worst texture  worst perimeter  worst area  \\\n",
       "0                   0.07871  ...          17.33           184.60      2019.0   \n",
       "1                   0.05667  ...          23.41           158.80      1956.0   \n",
       "2                   0.05999  ...          25.53           152.50      1709.0   \n",
       "3                   0.09744  ...          26.50            98.87       567.7   \n",
       "4                   0.05883  ...          16.67           152.20      1575.0   \n",
       "..                      ...  ...            ...              ...         ...   \n",
       "564                 0.05623  ...          26.40           166.10      2027.0   \n",
       "565                 0.05533  ...          38.25           155.00      1731.0   \n",
       "566                 0.05648  ...          34.12           126.70      1124.0   \n",
       "567                 0.07016  ...          39.42           184.60      1821.0   \n",
       "568                 0.05884  ...          30.37            59.16       268.6   \n",
       "\n",
       "     worst smoothness  worst compactness  worst concavity  \\\n",
       "0             0.16220            0.66560           0.7119   \n",
       "1             0.12380            0.18660           0.2416   \n",
       "2             0.14440            0.42450           0.4504   \n",
       "3             0.20980            0.86630           0.6869   \n",
       "4             0.13740            0.20500           0.4000   \n",
       "..                ...                ...              ...   \n",
       "564           0.14100            0.21130           0.4107   \n",
       "565           0.11660            0.19220           0.3215   \n",
       "566           0.11390            0.30940           0.3403   \n",
       "567           0.16500            0.86810           0.9387   \n",
       "568           0.08996            0.06444           0.0000   \n",
       "\n",
       "     worst concave points  worst symmetry  worst fractal dimension  target  \n",
       "0                  0.2654          0.4601                  0.11890       0  \n",
       "1                  0.1860          0.2750                  0.08902       0  \n",
       "2                  0.2430          0.3613                  0.08758       0  \n",
       "3                  0.2575          0.6638                  0.17300       0  \n",
       "4                  0.1625          0.2364                  0.07678       0  \n",
       "..                    ...             ...                      ...     ...  \n",
       "564                0.2216          0.2060                  0.07115       0  \n",
       "565                0.1628          0.2572                  0.06637       0  \n",
       "566                0.1418          0.2218                  0.07820       0  \n",
       "567                0.2650          0.4087                  0.12400       0  \n",
       "568                0.0000          0.2871                  0.07039       1  \n",
       "\n",
       "[569 rows x 31 columns]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.datasets import load_breast_cancer\n",
    "breast_cancer  = load_breast_cancer()\n",
    "data = pd.DataFrame(breast_cancer.data, columns=breast_cancer.feature_names);\n",
    "data['target'] = pd.Series(breast_cancer.target)\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "X=data.drop(columns=['target'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "y=data['target']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_label, X_test0, y_label, y_test0 = train_test_split( X, y, test_size=0.33, random_state=42)\n",
    "X_unlabel, X_test, y_unlabel, y_test = train_test_split( X_test0, y_test0, test_size=0.33, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们这里假设(X_train,y_train)为标记数据集，(X_unlabel,_)为无标记数据集。然后用半监督学习算法来学习出模型，来预测X_test得到结果y_pred,最后比较y_pred与y_test的准确率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 self-training实现代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.ensemble import RandomForestClassifier\n",
    "\n",
    "X_t=X_label\n",
    "y_t=y_label\n",
    "X_u=X_unlabel\n",
    "turns=0\n",
    "maxturn=1000\n",
    "confid=0.2\n",
    "clf = RandomForestClassifier(random_state=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "while len(X_u)>0 and turns<maxturn:\n",
    "    clf.fit(X_t, y_t)\n",
    "    y_p=clf.predict_proba(X_u)\n",
    "    droplst=[]\n",
    "    for i in range(y_p.shape[0]):\n",
    "        if y_p[i][0]<=confid:\n",
    "            #print(i,X_u.iloc[i], '0:',y_p[i][0])\n",
    "            X_t=X_t.append(X_u.iloc[i],ignore_index=True)\n",
    "            y_t=y_t.append(pd.Series([0]),ignore_index=True)\n",
    "            #X_u=X_u.drop(X_u.index[i])\n",
    "            droplst.append(X_u.index[i])\n",
    "        elif y_p[i][0]>=1-confid:\n",
    "            #print(i,X_u.iloc[i], '1:',y_p[i][0])\n",
    "            X_t=X_t.append(X_u.iloc[i],ignore_index=True)\n",
    "            y_t=y_t.append(pd.Series([1]),ignore_index=True)\n",
    "            #X_u=X_u.drop(X_u.index[i])\n",
    "            droplst.append(X_u.index[i])\n",
    "    X_u=X_u.drop(droplst)\n",
    "    turns+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.9047619047619048\n"
     ]
    }
   ],
   "source": [
    "from sklearn.metrics import accuracy_score\n",
    "y_pred=clf.predict(X_test)\n",
    "print(accuracy_score(y_test, y_pred)) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 约束种子k-means算法\n",
    "### 2.1 数据集选择\n",
    "采用经典鸢尾花数据集。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sepal length (cm)</th>\n",
       "      <th>sepal width (cm)</th>\n",
       "      <th>petal length (cm)</th>\n",
       "      <th>petal width (cm)</th>\n",
       "      <th>target</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>145</th>\n",
       "      <td>6.7</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.2</td>\n",
       "      <td>2.3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>146</th>\n",
       "      <td>6.3</td>\n",
       "      <td>2.5</td>\n",
       "      <td>5.0</td>\n",
       "      <td>1.9</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>147</th>\n",
       "      <td>6.5</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.2</td>\n",
       "      <td>2.0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>148</th>\n",
       "      <td>6.2</td>\n",
       "      <td>3.4</td>\n",
       "      <td>5.4</td>\n",
       "      <td>2.3</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>149</th>\n",
       "      <td>5.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>5.1</td>\n",
       "      <td>1.8</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>150 rows × 5 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "     sepal length (cm)  sepal width (cm)  petal length (cm)  petal width (cm)  \\\n",
       "0                  5.1               3.5                1.4               0.2   \n",
       "1                  4.9               3.0                1.4               0.2   \n",
       "2                  4.7               3.2                1.3               0.2   \n",
       "3                  4.6               3.1                1.5               0.2   \n",
       "4                  5.0               3.6                1.4               0.2   \n",
       "..                 ...               ...                ...               ...   \n",
       "145                6.7               3.0                5.2               2.3   \n",
       "146                6.3               2.5                5.0               1.9   \n",
       "147                6.5               3.0                5.2               2.0   \n",
       "148                6.2               3.4                5.4               2.3   \n",
       "149                5.9               3.0                5.1               1.8   \n",
       "\n",
       "     target  \n",
       "0         0  \n",
       "1         0  \n",
       "2         0  \n",
       "3         0  \n",
       "4         0  \n",
       "..      ...  \n",
       "145       2  \n",
       "146       2  \n",
       "147       2  \n",
       "148       2  \n",
       "149       2  \n",
       "\n",
       "[150 rows x 5 columns]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "\n",
    "iris=load_iris()\n",
    "rdata = pd.DataFrame(iris.data, columns=iris.feature_names);\n",
    "rdata['target'] = pd.Series(iris.target)\n",
    "rdata"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 约束种子k-means实现代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "from math import sqrt\n",
    "from sklearn import metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def readdata(df):\n",
    "    return df.iloc[:,:-1].values.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 读取种子集（有标签数据）\n",
    "def readseed(dataset, label):\n",
    "    wd=len(label)\n",
    "    #print(wd,len(label[0]))\n",
    "    seedset = defaultdict(list)\n",
    "    for i in range(wd):\n",
    "        for j in range(len(label[0])):\n",
    "            #print(i,'-append-',label[i][j],'-value-',dataset[label[i][j]])\n",
    "            seedset[i].append(dataset[label[i][j]])\n",
    "    return seedset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 输入：每一类的数据\n",
    "# 输出：这一类新的质心\n",
    "# 方法：求出这一类数据的总和求平均值\n",
    "def point_avg(points):\n",
    "    dimensions = len(points[0])\n",
    "    new_center = []\n",
    "    for dimension in range(dimensions):\n",
    "        sum = 0\n",
    "        # 求出每一列的数据总和\n",
    "        for p in points:\n",
    "            sum += p[dimension]\n",
    "        new_center.append(float(\"%.8f\" % (sum / float(len(points)))))\n",
    "    return new_center\n",
    "\n",
    "\n",
    "# 输入：数据集，质心数据，质心数量\n",
    "# 输出：新的质心数据\n",
    "# 功能：更新质心数据\n",
    "def update_centers(data_set, assignments, k):\n",
    "    # new_means，记录前一次学习的标签结果\n",
    "    new_means = defaultdict(list)\n",
    "    centers = []\n",
    "    for assignment, point in zip(assignments, data_set):\n",
    "        new_means[assignment].append(point)\n",
    "    for i in range(k):\n",
    "        # 逐一对每一类进行质心更新\n",
    "        points = new_means[i]\n",
    "        centers.append(point_avg(points))\n",
    "    return centers\n",
    "\n",
    "\n",
    "# 输入：数据集，质心\n",
    "# 输出：数组，每一个单元代表对应数据的类别。如assignment[0]=0，代表第0个数据的类别是第0类\n",
    "# 功能：求数据集每个单元数据的标签\n",
    "def assign_points(data_points, centers, label):\n",
    "    assignments = []\n",
    "    index = 0\n",
    "    for point in data_points:\n",
    "        flag = 1\n",
    "        # 有标签数据，直接填写对应标签\n",
    "        for k in range(len(label)):\n",
    "            if index in label[k]:\n",
    "                index = index+1\n",
    "                assignments.append(k)\n",
    "                flag = 0\n",
    "                break\n",
    "        if flag == 0:\n",
    "            continue\n",
    "        # 无标签数据求类别\n",
    "        # float('inf')表示正无穷\n",
    "        shortest = float('inf')\n",
    "        shortest_index = 0\n",
    "        # 取距离最近的质心的下标\n",
    "        for i in range(len(centers)):\n",
    "            value = distance(point, centers[i])\n",
    "            if value < shortest:\n",
    "                shortest = value\n",
    "                shortest_index = i\n",
    "        assignments.append(shortest_index)\n",
    "        index = index+1\n",
    "    return assignments\n",
    "\n",
    "\n",
    "# 求欧拉距离\n",
    "def distance(a, b):\n",
    "    dimention = len(a)\n",
    "    sum = 0\n",
    "    for i in range(dimention):\n",
    "        sq = (a[i] - b[i]) ** 2\n",
    "        sum += sq\n",
    "    return sqrt(sum)\n",
    "\n",
    "\n",
    "# 输入：数据集，质心个数\n",
    "# 输出：质心数据\n",
    "# 功能：用随机数的方法生成初始质心\n",
    "def generate_k(seedset, k):\n",
    "    centers = []\n",
    "    for i in range(k):\n",
    "        point = seedset[i]\n",
    "        centers.append(point_avg(point))\n",
    "    return centers\n",
    "\n",
    "\n",
    "def k_means(dataset, seedset, k, Y_train, label):\n",
    "    # 求初始质心\n",
    "    k_points = generate_k(seedset, k)\n",
    "    # 求标签\n",
    "    assignments = assign_points(dataset, k_points, label)\n",
    "    old_assignments = None\n",
    "\n",
    "    # 直到标签没变，停止\n",
    "    while assignments != old_assignments:\n",
    "        # 更新质心数据\n",
    "        new_centers = update_centers(dataset, assignments, k)\n",
    "        old_assignments = assignments\n",
    "        # 更新标签\n",
    "        assignments = assign_points(dataset, new_centers, label)\n",
    "\n",
    "    # 输出准确率\n",
    "    precision_rate = metrics.adjusted_rand_score(Y_train, assignments)\n",
    "    print('precision(Constrained Seed k-means): ',precision_rate)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "precision(Constrained Seed k-means):  0.7294203486015404\n"
     ]
    }
   ],
   "source": [
    "# 标签集\n",
    "label = [[0, 1, 8, 15, 26],\n",
    "         [51, 64, 78, 85, 92],\n",
    "         [105, 115, 127, 131, 148]]\n",
    "dataset = readdata(rdata)\n",
    "seedset = readseed(dataset, label)\n",
    "Y_train = rdata.target.tolist()\n",
    "k_means(dataset, seedset, 3, Y_train, label)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 约束K-Means算法\n",
    "### 3.1 数据集选择\n",
    "采用与2.1相同的鸢尾花数据集。\n",
    "### 3.2 约束K-Means实现代码"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "#[[34,44],[50,90],[110,140]]\n",
    "M=[[[4.9, 3.1, 1.5, 0.1],[5.1, 3.8, 1.9, 0.4]],\n",
    "  [[7.0, 3.2, 4.7, 1.4],[5.5, 2.6, 4.4, 1.2]],\n",
    "  [[6.5, 3.2, 5.1, 2.0],[6.7, 3.1, 5.6, 2.4]]]\n",
    "#[[1,100],[52,12],[120,20]]\n",
    "C=[[[4.9, 3.0, 1.4, 0.2],[6.3, 3.3, 6.0, 2.5]],\n",
    "  [[6.9, 3.1, 4.9, 1.5],[4.8, 3.0, 1.4, 0.1]],\n",
    "  [[6.9, 3.2, 5.7, 2.3],[5.4, 3.4, 1.7, 0.2]]]\n",
    "D=rdata.iloc[:,:-1].values.tolist()\n",
    "k=3\n",
    "maxturns=3000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "#从D中随机选取k个样本作为初始均值向量\n",
    "u=[]\n",
    "for i in range(k):\n",
    "    j=random.randint(0,len(D))\n",
    "    u.append(D[j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5.0, 2.3, 3.3, 1.0], [5.2, 4.1, 1.5, 0.1], [5.4, 3.9, 1.3, 0.4]]"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "u"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_nearest_cluster(i,d,K):\n",
    "    mind=d[i][0]\n",
    "    mink=0\n",
    "    for m in K:\n",
    "        if d[i][m]<mind:\n",
    "            mind=d[i][m]\n",
    "            mink=m\n",
    "    return mink"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isInCluster(y,B,r):\n",
    "    '''\n",
    "    检查y在B聚类簇r中是否存在\n",
    "    返回值：\n",
    "    1：存在\n",
    "    0：B中无y值\n",
    "    -1：不存在\n",
    "    '''\n",
    "    noExisted=True\n",
    "    for i in range(len(B)):\n",
    "        if y in B[i]:\n",
    "            noExisted = False\n",
    "            break\n",
    "    if noExisted == True:\n",
    "        return 0\n",
    "    if y in B[r]:\n",
    "        return 1\n",
    "    else:\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [],
   "source": [
    "def check_constrained(x,r,M,C,B):\n",
    "    '''\n",
    "    检查样本x划入聚类簇r，是否违背M和C中的约束。\n",
    "    M：必连约束\n",
    "    C：勿边约束\n",
    "    B: 聚类簇集合\n",
    "    返回值：True or False\n",
    "    '''\n",
    "    for i in range(len(M)):\n",
    "        if x == M[i][0]:\n",
    "            y=M[i][1]\n",
    "            #print('M left')\n",
    "        elif x==M[i][1]:\n",
    "            y=M[i][0]\n",
    "            #print('M right')\n",
    "        else:\n",
    "            continue\n",
    "        #检查y是否在B中的r聚类簇，如果是或者不存在，则返回true\n",
    "        if isInCluster(y,B,r)==-1:\n",
    "            return False\n",
    "    for i in range(len(C)):\n",
    "        if x == C[i][0]:\n",
    "            y=C[i][1]\n",
    "            #print('C left')\n",
    "        elif x==C[i][1]:\n",
    "            y=C[i][0]\n",
    "            #print('C right')\n",
    "        else:\n",
    "            continue\n",
    "        #检查y是否在B中的r聚类簇，如果否或者不存在，则返回true\n",
    "        if isInCluster(y,B,r)==1:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "noupdated=False\n",
    "turns=0\n",
    "toExit=False\n",
    "while noupdated==False and turns<=maxturns:\n",
    "    #print('k:',k)\n",
    "    B=[[] for n in range(k)]\n",
    "    #print('B:',B)\n",
    "    #print('len D:',len(D))\n",
    "    d=[]\n",
    "    rmlst=[]\n",
    "    for i in range(len(D)):\n",
    "        if toExit:\n",
    "            break;\n",
    "        a=[]\n",
    "        for j in range(k):\n",
    "            a.append(distance(D[i],u[j]))\n",
    "        d.append(a)\n",
    "        #print('a(',i,'):',a)\n",
    "        K=[n for n in range(k)]\n",
    "        #print('K:',K)\n",
    "        is_merged=False\n",
    "        is_voilated=False\n",
    "        while is_merged == False and toExit==False:\n",
    "            r=get_nearest_cluster(i,d,K)\n",
    "            #print('r:',r)\n",
    "            is_voilated=not check_constrained(D[i],r,M,C,B)\n",
    "            #print('voilated:',is_voilated)\n",
    "            if is_voilated==False:\n",
    "                B[r].append(D[i])\n",
    "                rmlst.append(i)\n",
    "                is_merged=True\n",
    "            else:\n",
    "                #print(K,r)\n",
    "                K.remove(r)\n",
    "                if len(K)==0:\n",
    "                    print('fail to training!')\n",
    "                    toExit=True\n",
    "                    break\n",
    "    if toExit:\n",
    "        break;\n",
    "    for i in range(k):\n",
    "        v=[]\n",
    "        for j in range(len(D[0])):#针对每个分簇中所有的样本的不同特征\n",
    "            newv=0\n",
    "            vl=[]\n",
    "            for n in range(len(B[i])):#针对每个分簇中所有的样本\n",
    "                newv+=B[i][n][j]/len(B[i])\n",
    "            vl.append(newv)\n",
    "        v.append(vl)\n",
    "    if u==v:\n",
    "        noupdated=True\n",
    "    turns+=1\n",
    "    if toExit:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1=[]\n",
    "t2=[]\n",
    "for i in range(k):\n",
    "    for j in range(len(B[i])):\n",
    "        t2=B[i][j]\n",
    "        t2.append(k-i-1)\n",
    "        t1.append(t2)\n",
    "#print(t1)\n",
    "\n",
    "t1.sort()\n",
    "\n",
    "D=rdata.iloc[:,:].values.tolist()\n",
    "D.sort()\n",
    "\n",
    "y_pred=np.array(t1)[:,-1]\n",
    "\n",
    "y_true=np.array(D)[:,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.6066666666666667\n"
     ]
    }
   ],
   "source": [
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "print(accuracy_score(y_true, y_pred)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
